package com.asuka.eva.service.impl;

import java.util.ArrayList;
import java.util.List;

public class SumCombinationFinder {

    public static List<List<Integer>> findCombinations(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<>();
        findCombinationsHelper(nums, target, 0, new ArrayList<>(), result);
        return result;
    }

    private static void findCombinationsHelper(int[] nums, int target, int index, List<Integer> current, List<List<Integer>> result) {
        if (target == 0) {
            result.add(new ArrayList<>(current));
            return;
        }
        if (target < 0 || index == nums.length) {
            return;
        }

        // Include the current number in the combination
        current.add(nums[index]);
        findCombinationsHelper(nums, target - nums[index], index, current, result);
        current.remove(current.size() - 1);

        // Skip the current number and move to the next one
        findCombinationsHelper(nums, target, index + 1, current, result);
    }

    public static void main(String[] args) {
        int[] nums = {3092,2005,3092,2569,2569,1998,2005,3276,2779,4930,1917,1998,2005,2005,2569,2005,2819,3283,1917,2989,2005,3092,2005,1998,3092,2819,2005,578,1917,3092,2005,3092,3092,1998,2029,2005,2569,2779,2005,2569,2569,2005,3092,3092};
        int target = 64468;
        List<List<Integer>> combinations = findCombinations(nums, target);

        if (combinations.isEmpty()) {
            System.out.println("No combinations found.");
        } else {
            System.out.println("Combinations that sum to " + target + ":");
            for (List<Integer> combination : combinations) {
                System.out.println(combination);
            }
        }
    }
}
